1. Field of the Invention
The present invention relates to generating, storing, and updating log-likelihood values when processing encoded data with a maximum a posteriori (MAP) algorithm.
2. Description of the Related Art
MAP decoding algorithms are employed for processing data input to a processor for detection and/or decoding operations. The algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. The MAP algorithm forms a trellis corresponding to possible states (portion of received symbol bits in the sequence) for each received output channel symbol per unit increment in time (i.e., clock cycle).
States, and transitions between states, of the Markov process spanning an interval of time may be represented by a trellis diagram. The number of bits that a state represents is equivalent to the memory of the Markov process. Thus, probabilities (sometimes of the form of log-likelihood values) are associated with each transition within the trellis, and probabilities are also associated with each decision for a symbol bit in the sequence.
The processor using the MAP algorithm computes log-likelihood values using xcex1 (forward state probabilities for states in the trellis) and xcex2 values (reverse state probabilities in the trellis), as described subsequently. The xcex1 values (a vector) are associated with states within the trellis, and these xcex1 values are stored in memory. The processor using the MAP algorithm then computes values of xcex2, and the xcex1 values are then retrieved from memory to compute the final output log-likelihood values. To compute the log-likelihood values, the entire state metric array of xcex1 values is stored by the MAP algorithm.
The variable Sk is defined as the state of the Markov process at time k, and yk is defined as the noisy channel output sample at time k, ymn is defined as the sequence ymn=(ym,ym+1, . . . yn) and, for a data block of length K, probability functions may be defined for the Markov process as given in equations (1) through (3):
xcex1sk=p(Sk=s;y1k)xe2x80x83xe2x80x83(1)
xcex2sk=p(yk+1K|Sk=s)xe2x80x83xe2x80x83(2)
xcex3sxe2x80x2,s=p(Sk=s;yk|Skxe2x88x921=sxe2x80x2).xe2x80x83xe2x80x83(3)
where s is the sequence defining the state Sk of the Markov process at time k.
In prior art decoders, calculation of the probability associated with a decision generally employs knowledge of a previous state Skxe2x88x921 sequence sxe2x80x2 at time kxe2x88x921 (complete state decisions and associated probabilities) of the decoder and the current state at time k. Thus, the algorithm computes the a posteriori probability (APP) value "sgr"k(sxe2x80x2,s)=p(Skxe2x88x921=sxe2x80x2;Sk=s|y1K) using the probabilities defined in equations (1) through (3). The APP value is then as given in equation (4):
"sgr"k(sxe2x80x2,s)=xcex1sxe2x80x2kxe2x88x921xcex3sxe2x80x2kxcex2skxe2x80x83xe2x80x83(4)
With the APP value for input uk, the log-likelihood value may then be calculated as given in equation (5):                               L          ⁡                      (                          u              k                        )                          =                  log          ⁢                      xe2x80x83                    ⁢                                    (                                                p                  ⁡                                      (                                                                  u                        k                                            =                                                                        +                          1                                                ❘                                                  y                          1                          K                                                                                      )                                                                    p                  ⁡                                      (                                                                  u                        k                                            =                                                                        -                          1                                                ❘                                                  y                          1                          K                                                                                      )                                                              )                        .                                              (        5        )            
In accordance with embodiments of the present invention, a maximum a posteriori (MAP) processor employs an algorithm that computes log-likelihood value with an a posteriori probability (APP) value employing a number N of previous state sequences greater than or equal to two (Nxe2x89xa72). The set of xcex1 values may be calculated for a current state and then reduced in accordance with an APP value based on previous state sequences. After forming the reduced set of xcex1 values, the full set of xcex2 values may be subsequently generated for calculation of log-likelihood values. By calculating a set of xcex1 values that may be decimated by, for example, N, the amount of memory required for to store the xcex1 values used in subsequent computations is reduced.
In accordance with an exemplary embodiment of the present invention, log-likelihood values are generated for data in a processor by a) generating a set of xcex1 values for a current state; and b) deleting selected values of the set of xcex1 values based on an a posteriori probability (APP) value having at least two previous states (Nxe2x89xa72) to provide a reduced set of xcex1 values corresponding to the data. The exemplary embodiment of the present invention further c) generates a set of xcex2 values for the current state; and d) calculates the log-likelihood values from the reduced set of xcex1 values and the set of xcex2 values.